/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-01-09
 * Time: 22:49
 */
public class Solution {
//     DP
//     dp[i][j] 表示前 i 个元素种, 有没有和为 j 的情况
    public boolean canPartition(int[] nums) {
        int len=nums.length;
        int sum=0;
        int max=0;
        for(int x: nums){
            sum+=x;
            max=Math.max(max,x);
        }
        if(sum%2==1){
            return false;
        }
        // 本题转化为 求有没有和为　sum/2 的情况
        int target=sum/2;
        if(max>target){
            return false;
        }
        boolean[][] dp=new boolean[len+1][target+1];
        for(int i=0;i<len;i++){
            for(int j=1;j<=target;j++){
                // 注意不要忘了, 不满足条件的情况
                if(j>nums[i]){
                    // 满足条件, 这个元素可取, 也可以不取
                    dp[i+1][j]=dp[i][j]||dp[i][j-nums[i]];
                }else if(j==nums[i]){
                    dp[i+1][j]=true;
                }else{
                    // 不满足条件, 这个元素不能取
                    dp[i+1][j]=dp[i][j];
                }
            }
            if(dp[i+1][target]){
                // 只要有和为 target 的情况直接返回
                return true;
            }
        }
        return dp[len][target];
    }
}